package com.example.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 *  示例 1:
 * 输入:[1,2,3,null,5,null,4]
 * 输出:[1,3,4]
 *
 *  示例 2:
 * 输入:[1,null,3]
 * 输出:[1,3]
 *
 *  示例 3:
 * 输入:[]
 * 输出:[]
 */
public class Leetcode199_RightSideView {
    public static void main(String[] args) {
        //       1
        //  2             3
        //      5              4
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        List<Integer> res = new Solution().rightSideView(root);

        res.forEach(e -> System.out.println(e));
    }

    static class Solution {

        /**
         * DFS
         * 按照根 -> 右 -> 左的顺序访问，就可以保证每层都是最先访问最右边的节点(将该节点加入到结果集中)
         * @param root
         * @return
         */
        private List<Integer> rightSideView2(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            int depth = 0;
            dfs(root, res, depth);
            return res;
        }

        private void dfs(TreeNode root, List<Integer> res, int depth) {
            if (root == null) return;
            // 访问当前节点
            if (depth == res.size()) // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
                res.add(root.val);

            depth++;
            dfs(root.right, res, depth);
            dfs(root.left, res, depth);
        }

        /**
         * 解法一:BFS(层序遍历)
         * 每一层的最右边的值即是看到的值
         * 将每层的最后一个加入到结果集中返回即可
         * @param root
         * @return
         */
        private List<Integer> rightSideView1(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);

            while (!queue.isEmpty()) {
                int curLayerSize = queue.size(); // 用于记录当前层的节点数
                while (curLayerSize > 0) {
                    TreeNode tmp = queue.poll();
                    if (tmp.left != null) queue.add(tmp.left);
                    if (tmp.right != null) queue.add(tmp.right);

                    if (curLayerSize == 1) res.add(tmp.val); // 将当前层的最后一个节点加入
                    --curLayerSize;
                }
            }

            return res;
        }

        public List<Integer> rightSideView(TreeNode root) {
            return rightSideView2(root);
        }

    }
}
